package likou;

import java.util.Arrays;

/**
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2021/01/02 09:43
 */
public class _239 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(maxSlidingWindow(new int[]{1,3,-1,-3,5,3,6,7},3)));
    }

    public static int[] maxSlidingWindow(int[] nums, int k) {
        //初始化队列两头
        int left = 0, right = left + k - 1;
        int[] ans;
        if(k>=nums.length){
            ans = new int[1];
        }else{
            ans = new int[nums.length-k+1];
        }
        if(right>nums.length-1){
            right = nums.length-1;
        }
        int count = 0;
        int index = maxnum(nums,left,right+1);
        ans[count] = nums[index];
        left++;
        right++;
        count++;
        while(right<nums.length){
            if(left<=index){
                if(nums[right]>=nums[index]){
                    index = right;
                    ans[count] = nums[index];
                }else{
                    ans[count] = nums[index];
                }
            }else{
                if(nums[left]==nums[index]||nums[left]==nums[index]-1){
                    index = left;
                    if(nums[right]>nums[index]){
                        index = right;
                    }
                    ans[count] = nums[index];
                }else{
                    index = maxnum(nums,left,right+1);
                    ans[count] = nums[index];
                }
            }
            left++; right++; count++;
        }
        return ans;
    }

    private static int maxnum(int[] nums, int start, int end){
        int index = start;
        for(int i=start+1;i<end;i++){
            if(nums[i]>nums[index]){
                index = i;
            }
        }
        return index;
    }
}

